﻿using System;
using System.Collections.Generic;

namespace Framework
{
    public class Heap<T> where T : IComparable<T>
    {
        int HeapSize;
        T[] Data;
        int capacity;

        public Heap(int capacity)
        {
            this.capacity = capacity;
            Clear();
        }

        public bool IsEmpty()
        {
            return HeapSize == 0;
        }

        public void Clear()
        {
            HeapSize = 0;
            Data = new T[capacity]; ;
        }

        public T this[int key]
        {
            get
            {
                return Data[key];
            }
        }

        public void Push(T value)
        {
            int newIndex;
            int parentIndex = parent(HeapSize);
            if (HeapSize >= Data.Length)
            {
                var newData = new T[Data.Length * 2]; 
                Array.Copy(Data, newData, Data.Length);
                Data = newData;
            }
            for (newIndex = HeapSize; newIndex > 0 && value.CompareTo(Data[parentIndex]) < 0; newIndex = parentIndex, parentIndex = parent(newIndex))
            {
                Data[newIndex] = Data[parentIndex];
            }
            Data[newIndex] = value;
            HeapSize++;
        }

        public T peak()
        {
            return Data[0];
        }

        public void Remove(T item)
        {
            int index = Array.IndexOf(Data, item);
            RemoveAt(index);
        }

        public void RemoveAt(int index)
        {
            if (index >= 0 && index < HeapSize)
            {
                int i, child;
                int tempHs = HeapSize - 1;
                T last = Data[tempHs];
                for (i = index; (child = left(i)) < HeapSize; i = child)
                {
                    /* Find highest priority child */
                    int rightChild = child + 1;

                    child += (rightChild < HeapSize) && Data[rightChild].CompareTo(Data[child]) < 0 ? 1 : 0;

                    if (last.CompareTo(Data[child]) < 0)
                        break;
                    Data[i] = Data[child];
                }
                Data[i] = last;
                HeapSize--;
            }
        }

        public T pop()
        {
            T min = Data[0];
            RemoveAt(0); 
            return min;
        }

        public int size()
        {
            return HeapSize;
        }

        static int left(int nodeIndex)
        {
            return (nodeIndex << 1) + 1;
        }

        static int parent(int nodeIndex)
        {
            return (nodeIndex - 1) >> 1;
        }

    }

    public class Heap<T, E> where E : IComparer<T>
    {
        int DEFAULT_CAPACITY = 16;

        int HeapSize;
        T[] Data;
        E comparator;

        public Heap(E comparator)
        {
            HeapSize = 0;
            Data = new T[DEFAULT_CAPACITY];
            this.comparator = comparator;
        }

        public bool IsEmpty()
        {
            return HeapSize == 0;
        }

        public void Clear()
        {
            HeapSize = 0;
        }

        public T this[int key]
        {
            get
            {
                return Data[key];
            }
        }

        public void Push(T value)
        {
            int newIndex;
            int parentIndex = parent(HeapSize);
            if (HeapSize >= Data.Length)
            {
                Data = new T[Data.Length * 2];
            }

            for (newIndex = HeapSize; newIndex > 0 && comparator.Compare(value, Data[parentIndex]) < 0; newIndex = parentIndex, parentIndex = parent(newIndex))
            {
                Data[newIndex] = Data[parentIndex];
            }
            Data[newIndex] = value;
            HeapSize++;
        }

        public T peak()
        {
            return Data[0];
        }

        public T pop()
        {
            int i, child;
            //try to avoid LHS
            int tempHs = HeapSize - 1;
            
            T min = Data[0];
            T last = Data[tempHs];

            for (i = 0; (child = left(i)) < tempHs; i = child)
            {
                /* Find highest priority child */
                int rightChild = child + 1;

                child += (rightChild < tempHs) && comparator.Compare(Data[rightChild], Data[child]) < 0 ? 1 : 0;

                if (comparator.Compare(last, Data[child]) < 0)
                    break;
                Data[i] = Data[child];
            }
            Data[i] = last;
            return min;
        }

        public int size()
        {
            return HeapSize;
        }

        static int left(int nodeIndex)
        {
            return (nodeIndex << 1) + 1;
        }

        static int parent(int nodeIndex)
        {
            return (nodeIndex - 1) >> 1;
        }

    }

    public class MinHeapComparator : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            if (x < y)
                return -1;
            else
                return 1;
        }
    }

    public class MaxHeapComparator : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            if (x < y)
                return 1;
            else
                return -1;
        }
    }

}
